#include<iostream>
#include<stack>
#include<cstring>

using namespace std; 
 
const unsigned int N = 256;
const unsigned int M = 2 * N;
const unsigned long long MAX = 0xffffffffffff;

class Buffer {
public:
	unsigned int bits;
	char ch;
};
 
class HuffmanTree;
 
class treeNode {
	friend HuffmanTree;
private:
	unsigned long long weight;
	unsigned int right, left;
	unsigned int parents;
};
 
class HuffmanTree {
private:
	treeNode nodes[M];
	unsigned int leaf[N];
	unsigned int index[N];
	char* leafCode[N];
	FILE* input, *output;
	unsigned int num;
	unsigned long long size;
	Buffer buf;
 
	void write(unsigned int i);
	void write(unsigned int num, unsigned int bits);
	void writerest();
	void read(unsigned int &i);
	void read(unsigned int &num, unsigned int bits);
 
	void enSieve();
	void select(unsigned int pos,unsigned int &t1,unsigned int &t2);
	void enSetTree();
 
public:
	void Encode();
};

void HuffmanTree::write(unsigned int i) {
	buf.ch = (buf.ch << 1) + i;
	buf.bits++;
	if (buf.bits == 8) {
		fputc(buf.ch, output);
		buf.bits = 0;
		buf.ch = 0;
	}
}
void HuffmanTree::write(unsigned int target, unsigned int bits) {
	stack<unsigned int> s;
	unsigned int i, bit;
	for (i = 1; i <= bits; i++) {
	s.push(target & 1);
	target = (target >> 1);
	}
	for (i = 1; i <= bits; i++) {
	bit = s.top();
	write(bit);
	s.pop();
	}
}
void HuffmanTree::writerest() {
	unsigned int now = buf.bits;
	if (now>0)
		for (unsigned int i = 0; i<8 - now; i++)write(0);
}
void HuffmanTree::read(unsigned int &i) {
	if (buf.bits == 0) {
		buf.bits = 8;
		buf.ch = fgetc(input);
	}
	i = (buf.ch & 128) >> 7;
	buf.bits--;
	buf.ch <<= 1;
 
}
void HuffmanTree::read(unsigned int &target, unsigned int bits) {
	unsigned int tmp;
	target = 0;
	for (unsigned int i = 0; i < bits; ++i) {
		read(tmp);
		target = (target << 1) + tmp;
	}
}

void HuffmanTree::enSieve() {
	char inName[1000], outName[1000];
	cin >> inName;
	strcpy(outName, inName);
    char *dotPos = strrchr(outName, '.');
    if (dotPos != nullptr) {
        strcpy(dotPos, ".huf");
    } else {
        strcat(outName, ".huf");
    }
	if ((input = fopen(inName, "rb")) == NULL) {
		cout << "Can not open file." << endl;
		system("pause");
		exit(1);
	}
	if (feof(input)) {
		cout << "Empty source file" << endl;
		system("pause");
		exit(1);
	}
	if ((output = fopen(outName, "wb")) == NULL) {
		cout << "Can not open file." << endl;;
		system("pause");
		exit(1);
	}
 
	rewind(input);
	unsigned int ch;
	size = 0;
	for (unsigned int i = 0; i < N; ++i) {
		leaf[i] = 0;
		index[i] = 0;
	}
	for (unsigned int i = 0; i < M; ++i) {
		nodes[i].weight = 0;
		nodes[i].left = nodes[i].right = nodes[i].parents = M-1;
	}
	ch = fgetc(input);
	while (!feof(input)) {
		leaf[ch]++;
		size++;
		ch = fgetc(input);
	}
 
	nodes[M-1].weight = MAX;
 
	num = 0;
	for (unsigned int i = 0; i < N; ++i)
		if (leaf[i]) {
			nodes[num].weight = leaf[i];
			leaf[i] = num;
			index[num] = i;
			num++;
		}
	if (!num) {
		cout << "doesn't have a word" << endl;
		system("pause");
		exit(1);
	}
}

void HuffmanTree::select(unsigned int pos, unsigned int &t1,unsigned int &t2) {
	t1 = M-1, t2 = M-1;
	for (unsigned int i = 0; i < pos; ++i) {
		if (nodes[i].weight < nodes[t1].weight&&nodes[i].parents==M-1)
			t1 = i;
	}
	for (unsigned int i = 0; i < pos; ++i) {
		if (nodes[i].weight < nodes[t2].weight&&i != t1&&nodes[i].parents == M-1)
			t2 = i;
	}
}

 
void HuffmanTree::enSetTree() {
	for (unsigned int i = num; i < num * 2 - 1; ++i) {
		unsigned int t1, t2;
		select(i, t1, t2);
		nodes[i].weight = nodes[t1].weight + nodes[t2].weight;
		nodes[i].left = t1;
		nodes[i].right = t2;
		nodes[t1].parents = nodes[t2].parents = i;
	}
 
	for (int i = 0; i < N; ++i)
		leafCode[i] = NULL;
 
	unsigned int start, c, f, i;
	char *cd = new char[num];
	for (i = 0; i < N; i++)
		if (leafCode[i] != NULL) {
			delete[]leafCode[i];
			leafCode[i] = NULL;
		}
	cd[num - 1] = '\0';
	for (i = 0; i < num; i++) {
		start = num - 1;
		for (c = i, f = nodes[i].parents; f != M - 1; c = f, f = nodes[c].parents) {
			if (nodes[f].left == c)cd[--start] = '0';
			else cd[--start] = '1';
		}
		leafCode[i] = new char[num - start];
		strcpy(leafCode[i], &cd[start]);
	}
	delete cd;
}

 
void HuffmanTree::Encode() {
	enSieve();
	enSetTree();
 
	rewind(output);
	rewind(input);

	buf.bits = 0;
	buf.ch = 0;
	fwrite(&size,sizeof(unsigned long long),1,output);
	write(num, 8);
	for (unsigned int i = 0; i < num; ++i)
		fwrite(&index[i], sizeof(char), 1, output);
	unsigned maxbit = 1;
	unsigned int tmp = num * 2 - 1;
	while (tmp) {
		maxbit++;
		tmp >>= 1;
	}
	for (unsigned int i = num; i < num * 2 - 1; ++i) {
		write(nodes[i].left, maxbit);
		write(nodes[i].right, maxbit);
	}
 
	unsigned int ch;
	ch = fgetc(input);
	while (!feof(input)) {
		unsigned int start = 0;
		while (leafCode[leaf[ch]][start] != '\0') {
			if (leafCode[leaf[ch]][start] == '1')write(1);
			else write(0);
			++start;
		}
		ch = fgetc(input);
	}
	writerest();
	cout << "Done!\n";
	fclose(input);
	fclose(output);
}

int main(void) {
	HuffmanTree tree;
	tree.Encode();
	return 0;
}
